As knowledge graphs (that is, graph structures with attributes on vertices and edges) have become increasingly popular, efficient retrieval of information from large interconnected data has become increasingly challenging. While existing graph databases can be tuned for queries that explore relationships, the performance of analytics operations involving constraints on attributes associated with the traversal is commonly lacking. Further, existing external indexing engines cannot be effectively used directly with knowledge graphs.